/*
==================================================================
* 版权所有 © 2025 CaryXiong
* Copyright (C) 2025 CaryXiong(a1816101108@outlook.com)
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
===================================================================
*/




#include <iostream>
using namespace std;

const int MaxSize = 100;

template<typename DataType>
class SeqList{
    public:
    	//初始化线性表
    	SeqList();
        //创建一个线性表
        SeqList(DataType a[], int n);
        ~SeqList();
        void PrintList();
        int Length();
        int Locate(DataType x);
        DataType Get(int i);
        void Insert(DataType value, int i);
        DataType Delete(int i);
        bool Empty();
        DataType FindMax();
        DataType FindMin();
        DataType Sum();
        DataType Average();
        void Ascending_Sort();
        void Descending_Sort();
        int Locate2(DataType x);
        void Inverse();
        void Insert2(int i, DataType x);
        int Insert3(DataType x);
        int Delete2();
        int Delete3();

    private:
    	DataType *data = new DataType[MaxSize];
        int length;
};

template<typename DataType>
SeqList<DataType> :: SeqList(){
    DataType a[0];
    length = 0;
}

template<typename DataType>
SeqList<DataType> :: SeqList(DataType a[], int n){
    if(n>MaxSize)throw "参数非法";
    for(int i=0; i<n; i++) data[i] = a[i];
    length = n;
}

template<typename DataType>
SeqList<DataType> :: ~SeqList(){
    delete []data;
}

template<typename DataType>
void SeqList<DataType> :: PrintList(){
    for(int i=0; i<length; i++) cout << data[i] << "\t";
    cout << endl;
}

template<typename DataType>
int SeqList<DataType> :: Length(){
    return length;
}

template<typename DataType>
int SeqList<DataType> :: Locate(DataType x){
    for(int i=0; i<length; i++){
        if(data[i] == x) return i+1;
    }
    throw "查找失败";
}

template<typename DataType>
DataType SeqList<DataType> :: Get(int i){
    if(i>length) throw "超出范围";
    else return data[i-1];
}

template<typename DataType>
void SeqList<DataType> :: Insert(DataType value, int i){
    if(length == MaxSize) throw "表满";
    else if(i<1 || i>length+1) throw "插入位置错误";
    else for(int j=length; j>=i; j--) data[j] = data[j-1];
    data[i-1] = value;
    length ++;
}

template<typename DataType>
DataType SeqList<DataType> :: Delete(int i){
    DataType x;
    if(i<1 || i>length) throw "删除位置错误";
    else{
        x = data[i-1];
        for(int j=i; j<=length; j++) data[j-1] = data[j];
        length--;
        return x;
    }
}

template<typename DataType>
bool SeqList<DataType> :: Empty(){
    if(length == 0) return true;
    else return false;
}

template<typename DataType>
DataType SeqList<DataType> :: FindMax(){
    if(length == 0) throw "空表不可查找";
    DataType max = data[0];
    int pos = 0;
    for(int i=1; i<length; i++){
        if(data[i] > max){
            max = data[i];
            pos = i;
        }
    }
    return max;
}

template<typename DataType>
DataType SeqList<DataType> :: FindMin(){
    if(length == 0) throw "空表不可查找";
    DataType min = data[0];
    int pos = 0;
    for(int i=1; i<length; i++){
        if(data[i] < min){
            min = data[i];
            pos = i;
        }
    }
    return min;
}

template<typename DataType>
DataType SeqList<DataType> :: Sum(){
    if(length == 0) throw "空表不可求和";
    DataType sum = 0;
    for(int i=0; i<length; i++) sum+=data[i];
    return sum;
}

template<typename DataType>
DataType SeqList<DataType> :: Average(){
    if(length == 0) throw "空表不可求和";
    DataType ave = Sum() / length;
    return ave;
}

template<typename DataType>
void SeqList<DataType> :: Ascending_Sort(){
    if(length == 0) throw "空表不可排序";
    DataType temp;
    for(int i=length-1; i>0; i--){
        for(int j=0; j<i; j++){
            if(data[j]>data[j+1]){
                temp = data[j];
                data[j] = data[j+1];
                data[j+1] = temp;
            }
        }
    }
    PrintList();
}

template<typename DataType>
void SeqList<DataType> :: Descending_Sort(){
    if(length == 0) throw "空表不可排序";
    DataType temp;
    for(int i=length-1; i>0; i--){
        for(int j=0; j<i; j++){
            if(data[j]<data[j+1]){
                temp = data[j];
                data[j] = data[j+1];
                data[j+1] = temp;
            }
        }
    }
    PrintList();
}

template<typename DataType>
int SeqList<DataType> :: Locate2(DataType x){
    if(length == 0) throw "空表不可查找";
    for(int i=length-1; i>=0; i--){
        if(data[i] == x) return i+1;
    }
    throw "查找失败";
}

template<typename DataType>
void SeqList<DataType> :: Inverse(){
    // 该函数用于对数据表进行就地逆置
    DataType temp;
    if(length%2 == 0){
        for(int i=0; i<=length/2-1; i++){
            temp = data[i];
            data[i] = data[length-1-i];
            data[length-1-i] = temp;
        }
    }else{
        for(int i=0; i<=(length-3)/2; i++){
            temp = data[i];
            data[i] = data[length-1-i];
            data[length-1-i] = temp;
        }
    }
}

template<typename DataType>
void SeqList<DataType> :: Insert2(int i, DataType x){
    if(length == MaxSize) throw "表满";
    for(int j=0; j<length; j++) if(data[j] == x) throw "已有该元素 禁止插入";

    Insert(x, i);
}

// 可优化，具体函数在后

template<typename DataType>
int SeqList<DataType> :: Insert3(DataType x){
    // 该函数用于向已有的严格递增/递减顺序表中插入元素，插入完成的数据表依旧严格递增/递减

    // type:用于存储该顺序表的递增/递减特性    1:递增    0:递减
    int type;
    if(length < 2) throw "顺序表长度至少应为2";
    if(data[0] > data[1]) type = 0;
    if(data[1] > data[0]) type = 1;
    if(data[1] == data[0]) throw "该表不严格递增/递减";
    for(int i=0; i<length-1; i++){
        if(type == 0 && data[i]<=data[i+1]) throw "该表不严格递增/递减";
        if(type == 1 && data[i]>=data[i+1]) throw "该表不严格递增/递减";
    }

    cout << type << endl;

    for(int i=0; i<length; i++){
        if(type == 0){
            if(data[i]<x){
                Insert2(i+1, x);
                return i+1;
            }
            Insert2(length+1, x);
            return length;
        }
        if(type == 1){
            if(data[i]>x){
                Insert2(i+1, x);
                return i+1;
            }
            Insert2(length+1, x);
            return length;
        }
    }
    return 0;
}


template<typename DataType>
int SeqList<DataType> :: Insert3(DataType x){

    int type;
    if(length < 2) throw "顺序表长度至少应为2";
    if(data[0] > data[1]) type = 0;
    if(data[1] > data[0]) type = 1;
    if(data[1] == data[0]) throw "该表不严格递增/递减";
    for(int i=0; i<length-1; i++){
        if(type == 0 && data[i]<=data[i+1]) throw "该表不严格递增/递减";
        if(type == 1 && data[i]>=data[i+1]) throw "该表不严格递增/递减";
    }

    data[length] = x;
    length++;

    if(data[0] > data[1]) Descending_Sort();
    else Ascending_Sort();

    return Locate(x);
}


template<typename DataType>
int SeqList<DataType> :: Delete2(){
    //  删除相同元素 保留序号最小的一个
    int count = 0;
    for(int i=0; i<length; i++){
        for(int j=i+1; j<length; j++){
            if(data[i] == data[j]){
                Delete(j+1);
                count ++;
                j--;
            }
        }
    }
    return count;
}

/*
template<typename DataType>
int SeqList<DataType> :: Delete3(){
    //  删除相同元素 保留序号最大的一个
    int sum = 0;
    for(int i=length-1; i>=0; i--){
        for(int j=i-1; j>=0; j--){
            if(data[i] == data[j]){
                Delete(j+1);
                sum ++;
                j++;
            }
        }
    }
    return sum;
}
*/

template<typename DataType>
int SeqList<DataType> :: Delete3(){
    int count;
    //  删除相同元素 保留序号最大的一个
    Inverse();
    count = Delete2();
    Inverse();
    return count;
}



int main(){
	int r[5] = {1,2,2,2,1}, i, x;
	SeqList<int> L(r,5);
	cout << "当前线性表的数据为：";
	L.PrintList();

    cout << "线性表长度为：" << L.Length() << endl;
    cout << "查找元素位置结果：" << L.Locate(2) << endl;
    cout << "获取到第5个元素为：" << L.Get(5) << endl;
    L.Insert(1,5);
    cout << "将1插入到第5个位置，结果为：";
    L.PrintList();
    L.Delete(5);
    cout << "删除第5个元素，结果为：";
    L.PrintList();
    if(L.Empty()) cout << "表空" << endl;
    else cout << "表非空" << endl;
    cout << "查找表中最大值：" << L.FindMax() << endl;
    cout << "查找表中最小值：" << L.FindMin() << endl;
    cout << "对表中所有元素求和：" << L.Sum() << endl;
    cout << "对表中所有元素求平均：" << L.Average() << endl;
    cout << "对表中元素升序排列：";
    L.Ascending_Sort();
    cout << "对表中元素降序排列：";
    L.Descending_Sort();
    cout << endl << endl;


    int a[6] = {1,2,2,2,1,1};
    SeqList<int> L1(a,6);
	cout << "当前线性表的数据为：";
	L1.PrintList();
    cout << "查找最右侧的元素2位置：" << L1.Locate2(2) << endl;
    L1.Inverse();
    cout << "对表原地逆置：";
    L1.PrintList();
    try{
        L1.Insert2(3,2);
    }catch(const char *str){cout << str << endl;}
    L1.Delete2();
    cout << "删除相同元素，保留最左侧的一个：";
    L1.PrintList();
    
    int c[6] = {1,2,2,2,1,1};
    SeqList<int> L3(c,6);
    L3.Delete3();
    cout << "删除相同元素，保留最右侧的一个：";
    L3.PrintList();
    cout << endl << endl <<endl;



    int b[5] = {1,3,5,7,9};
    SeqList<int> L2(b,5);
	cout << "当前线性表的数据为：";
	L2.PrintList();
    cout << "按照递增/递减插入元素4：";
    L2.Insert3(4);

    system("pause");
    
}